/* Copyright 2007-2008 dnAnalytics Project.
 *
 * Contributors to this file:
 * Patrick van der Velde
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 * 
 * * Redistributions of source code must retain the above copyright notice, this 
 *   list of conditions and the following disclaimer.
 * * Redistributions in binary form must reproduce the above copyright notice, 
 *   this list of conditions and the following disclaimer in the documentation
 *   and/or other materials provided with the distribution.
 * * Neither the name of the dnAnalytics Project nor the names of its contributors
 *   may be used to endorse or promote products derived from this software without
 *   specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
 * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

using System;
using System.Diagnostics;

namespace dnAnalytics.LinearAlgebra.Solvers
{
    /// <summary>
    /// Monitors an iterative calculation for signs of divergence.
    /// </summary>
    public sealed class DivergenceStopCriterium : IIterationStopCriterium
    {
        /// <summary>
        /// Defines the default maximum residual increase.
        /// </summary>
        private const double s_DefaultMaximumRelativeIncrease = 0.08;

        /// <summary>
        /// Defines the default number of tracking iterations.
        /// </summary>
        private const int s_DefaultMinimumIterations = 10;

        /// <summary>
        /// Defines the default last iteration number. Set to -1 because iterations normally
        /// start at 0.
        /// </summary>
        private const int sm_DefaultLastIterationNumber = -1;

        /// <summary>
        /// The default status.
        /// </summary>
        private static readonly ICalculationStatus sm_DefaultStatus = new CalculationIndetermined();

        /// <summary>
        /// Returns the default value for the maximum relative increase that the 
        /// residual may experience before a divergence warning is issued.
        /// </summary>
        public static double DefaultMaximumRelativeIncrease
        {
            get
            {
                return s_DefaultMaximumRelativeIncrease;
            }
        }

        /// <summary>
        /// Returns the default value for the minimum number of iterations over which 
        /// the residual must grow before a divergence warning is issued.
        /// </summary>
        public static int DefaultMinimumNumberOfIterations
        {
            get
            {
                return s_DefaultMinimumIterations;
            }
        }

        /// <summary>
        /// The maximum relative increase the residual may experience without triggering a divergence warning.
        /// </summary>
        private double m_MaximumRelativeIncrease;

        /// <summary>
        /// The number of iterations over which a residual increase should be tracked before
        /// issuing a divergence warning.
        /// </summary>
        private int m_MinimumNumberOfIterations;

        /// <summary>
        /// The status of the calculation
        /// </summary>
        private ICalculationStatus m_Status = sm_DefaultStatus;

        /// <summary>
        /// The array that holds the tracking information.
        /// </summary>
        private double[] m_ResidualHistory;

        /// <summary>
        /// The iteration number of the last iteration.
        /// </summary>
        private int m_LastIteration = sm_DefaultLastIterationNumber;

        /// <summary>
        /// Creates an instance of the <c>DivergenceStopCriterium</c> class with the default maximum 
        /// relative increase and the default minimum number of tracking iterations.
        /// </summary>
        public DivergenceStopCriterium()
            : this(s_DefaultMaximumRelativeIncrease, s_DefaultMinimumIterations)
        {
        }

        /// <summary>
        /// Creates an instance of the <c>DivergenceStopCriterium</c> class with the specified maximum 
        /// relative increase and the default minimum number of tracking iterations.
        /// </summary>
        /// <param name="maximumRelativeIncrease">
        ///   The maximum relative increase that the residual may experience before a 
        ///   divergence warning is issued.
        /// </param>
        public DivergenceStopCriterium(double maximumRelativeIncrease)
            : this(maximumRelativeIncrease, s_DefaultMinimumIterations)
        {
        }

        /// <summary>
        /// Creates an instance of the <c>DivergenceStopCriterium</c> class with the default maximum 
        /// relative increase and the specified minimum number of tracking iterations.
        /// </summary>
        /// <param name="minimumIterations">
        ///   The minimum number of iterations over which the residual must grow before a
        ///   divergence warning is issued.
        /// </param>
        public DivergenceStopCriterium(int minimumIterations)
            : this(s_DefaultMaximumRelativeIncrease, minimumIterations)
        {
        }

        /// <summary>
        /// Creates an instance of the <c>DivergenceStopCriterium</c> class with the specified maximum 
        /// relative increase and the specified minimum number of tracking iterations.
        /// </summary>
        /// <param name="maximumRelativeIncrease">
        ///   The maximum relative increase that the residual may experience before a 
        ///   divergence warning is issued.
        /// </param>
        /// <param name="minimumIterations">
        ///   The minimum number of iterations over which the residual must grow before a
        ///   divergence warning is issued.
        /// </param>
        public DivergenceStopCriterium(double maximumRelativeIncrease, int minimumIterations)
        {
            if (maximumRelativeIncrease <= 0)
            {
                throw new ArgumentOutOfRangeException("maximumRelativeIncrease");
            }

            // There must be at least three iterations otherwise we can't calculate
            // the relative increase
            if (minimumIterations < 3)
            {
                throw new ArgumentOutOfRangeException("minimumIterations");
            }

            m_MaximumRelativeIncrease = maximumRelativeIncrease;
            m_MinimumNumberOfIterations = minimumIterations;
        }

        /// <summary>
        /// Gets or sets the maximum relative increase that the residual may experience before a
        /// divergence warning is issued.
        /// </summary>
        /// <exception cref="ArgumentOutOfRangeException">Thrown if the <c>Maximum</c> is set to zero or below.</exception>
        public double MaximumRelativeIncrease
        {
            [DebuggerStepThrough]
            get
            {
                return m_MaximumRelativeIncrease;
            }
            [DebuggerStepThrough]
            set
            {
                if (value <= 0)
                {
                    throw new ArgumentOutOfRangeException("value");
                }

                m_MaximumRelativeIncrease = value;
            }
        }

        /// <summary>
        /// Returns the maximum relative increase to the default.
        /// </summary>
        public void ResetMaximumRelativeIncreaseToDefault()
        {
            m_MaximumRelativeIncrease = s_DefaultMaximumRelativeIncrease;
        }

        /// <summary>
        /// Gets or sets the minimum number of iterations over which the residual must grow before
        /// issuing a divergence warning.
        /// </summary>
        /// <exception cref="ArgumentOutOfRangeException">Thrown if the <c>value</c> is set to less than one.</exception>
        public int MinimumNumberOfIterations
        {
            [DebuggerStepThrough]
            get
            {
                return m_MinimumNumberOfIterations;
            }
            [DebuggerStepThrough]
            set
            {
                // There must be at least three iterations otherwise we can't calculate
                // the relative increase
                if (value < 3)
                {
                    throw new ArgumentOutOfRangeException("value");
                }

                m_MinimumNumberOfIterations = value;
            }
        }

        /// <summary>
        /// Returns the minimum number of iterations to the default.
        /// </summary>
        public void ResetNumberOfIterationsToDefault()
        {
            m_MinimumNumberOfIterations = s_DefaultMinimumIterations;
        }

        /// <summary>
        /// Determines the status of the iterative calculation based on the stop criteria stored
        /// by the current <c>IIterationStopCriterium</c>.
        /// </summary>
        /// <param name="iterationNumber">The number of iterations that have passed so far.</param>
        /// <param name="solutionVector">The vector containing the current solution values.</param>
        /// <param name="sourceVector">The right hand side vector.</param>
        /// <param name="residualVector">The vector containing the current residual vectors.</param>
        /// <returns>
        ///   An <c>ICalculationStatus</c> which indicates what the status of the iterative 
        ///   calculation is according to the current <c>IIterationStopCriterium</c>.
        /// </returns>
        /// <remarks>
        /// The individual stop criteria may internally track the progress of the calculation based
        /// on the invocation of this method. Therefore this method should only be called if the 
        /// calculation has moved forwards at least one step.
        /// </remarks>
        public void DetermineStatus(int iterationNumber, Vector solutionVector, Vector sourceVector, Vector residualVector)
        {
            if (iterationNumber < 0)
            {
                throw new ArgumentOutOfRangeException("iterationNumber");
            }

            if (residualVector == null)
            {
                throw new ArgumentNullException("residualVector");
            }

            if (m_LastIteration >= iterationNumber)
            {
                // We have already stored the actual last iteration number
                // For now do nothing. We only care about the next step.
                return;
            }

            if ((m_ResidualHistory == null) || (m_ResidualHistory.Length != RequiredHistoryLength))
            {
                CreateResidualHistoryStorage();
            }

            // We always track the residual.
            // Move the old versions one element up in the array.
            for (int i = 1; i < m_ResidualHistory.Length; i++)
            {
                m_ResidualHistory[i - 1] = m_ResidualHistory[i];
            }

            // Store the infinity norms of both the solution and residual vectors
            // These values will be used to calculate the relative drop in residuals
            // later on.
            m_ResidualHistory[m_ResidualHistory.Length - 1] = residualVector.InfinityNorm();

            // Check if we have NaN's. If so we've gone way beyond normal divergence.
            // Stop the iteration.
            if (double.IsNaN(m_ResidualHistory[m_ResidualHistory.Length - 1]))
            {
                SetStatusToDiverged();
                return;
            }

            // Check if we are diverging and if so set the status
            if (IsDiverging())
            {
                SetStatusToDiverged();
            }
            else
            {
                SetStatusToRunning();
            }

            m_LastIteration = iterationNumber;
        }

        private bool IsDiverging()
        {
            // Run for each variable
            for (int i = 1; i < m_ResidualHistory.Length; i++)
            {
                double difference = m_ResidualHistory[i] - m_ResidualHistory[i - 1];
                // Divergence is occurring if:
                // - the last residual is larger than the previous one
                // - the relative increase of the residual is larger than the setting allows
                if ((difference < 0) || (m_ResidualHistory[i - 1] * (1 + m_MaximumRelativeIncrease) >= m_ResidualHistory[i]))
                {
                    // No divergence taking place within the required number of iterations
                    // So reset and stop the iteration. There is no way we can get to the
                    // required number of iterations anymore.
                    return false;
                }
            }

            return true;
        }

        private int RequiredHistoryLength
        {
            [DebuggerStepThrough]
            get
            {
                return m_MinimumNumberOfIterations + 1;
            }
        }

        private void CreateResidualHistoryStorage()
        {
            m_ResidualHistory = new double[RequiredHistoryLength];
        }

        private void SetStatusToDiverged()
        {
            if (!(m_Status is CalculationDiverged))
            {
                m_Status = new CalculationDiverged();
            }
        }

        private void SetStatusToRunning()
        {
            if (!(m_Status is CalculationRunning))
            {
                m_Status = new CalculationRunning();
            }
        }

        /// <summary>
        /// Returns the current calculation status.
        /// </summary>
        public ICalculationStatus Status
        {
            [DebuggerStepThrough]
            get
            {
                return m_Status;
            }
        }

        /// <summary>
        /// Resets the <c>IIterationStopCriterium</c> to the pre-calculation state.
        /// </summary>
        public void ResetToPrecalculationState()
        {
            m_Status = sm_DefaultStatus;
            m_LastIteration = sm_DefaultLastIterationNumber;
            m_ResidualHistory = null;
        }

        /// <summary>
        /// Returns the <c>StopLevel</c> which indicates what sort of stop criterium this
        /// <c>IIterationStopCriterium</c> monitors.
        /// </summary>
        /// <value>Returns <see cref="dnAnalytics.LinearAlgebra.Solvers.StopLevel.Divergence"/>.</value>
        public StopLevel StopLevel
        {
            [DebuggerStepThrough]
            get
            {
                return StopLevel.Divergence;
            }
        }

        /// <summary>
        /// Clones the current <c>DivergenceStopCriterium</c> and its settings.
        /// </summary>
        /// <returns>A new instance of the <c>DivergenceStopCriterium</c> class.</returns>
        public IIterationStopCriterium Clone()
        {
            return new DivergenceStopCriterium(m_MaximumRelativeIncrease, m_MinimumNumberOfIterations);
        }

        object ICloneable.Clone()
        {
            return Clone();
        }
    }
}
